package _hash;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/*
349. 两个数组的交集
  https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html
  https://leetcode.cn/problems/intersection-of-two-arrays/description/

  示例 1：

  输入：nums1 = [1,2,2,1], nums2 = [2,2]
  输出：[2]

  示例 2：
  输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  输出：[9,4]
  解释：[4,9] 也是可通过的
 */
public class leetcode_349_Java {
    @Test
    public void test_1() {
        int[] nums1 = new int[]{1, 2, 2, 1}, nums2 = new int[]{2, 2};
        int[] actual = intersection(nums1, nums2);
        int[] expect = new int[]{2};
        Assert.assertEquals(Arrays.toString(actual), Arrays.toString(expect));
    }

    @Test
    public void test_2() {
        int[] nums1 = new int[]{4, 9, 5}, nums2 = new int[]{9, 4, 9, 8, 4};
        int[] actual = intersection(nums1, nums2);
        int[] expect = new int[]{4, 9};
        Assert.assertEquals(Arrays.toString(expect), Arrays.toString(actual));
    }


    public int[] intersection(int[] nums1, int[] nums2) {
        return intersection1(nums1, nums2);
//        return intersection2(nums1, nums2);
    }

    public int[] intersection1(int[] nums1, int[] nums2) {
        /*
         方法1:
         遍历 num1， 把num1 存入Set。
         遍历 num2，如果存在set，则放入list
         list -> Array
         */

        // T - N
        // S - N
        HashSet<Integer> set = new HashSet<>();
        for (int v : nums1) {
            set.add(v);
        }

        HashSet<Integer> set2 = new HashSet<>();
        for (int v : nums2) {
            if (set.contains(v)) {
                set2.add(v);
            }
        }

        int size = set2.size();
        int[] array = new int[size];
        int i = 0;
        for (int v : set2) {
            array[i] = v;
            i++;
        }
        return array;
    }

    public int[] intersection2(int[] nums1, int[] nums2) {
        /*
         * 把num1 放入 array a (1001)
         * 把num2 放入 array b ((1001)
         * loop [0,1000],item 在 a 和 b，则放入 list
         * list 转成 array
         */
        int[] a = new int[1001];
        int[] b = new int[1001];
        for (int v : nums1) {
            a[v]++;
        }
        for (int v : nums2) {
            b[v]++;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i <= 1000; i++) {
            if (a[i] > 0 && b[i] > 0) {
                list.add(i);
            }
        }
        int size = list.size();
        int[] result = new int[size];
        for (int i = 0; i <= size - 1; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}